As is known in the art, one type of packet transmission network is a wireless transmission network. As is also known, Wireless Local Area Networks (WLAN) are becoming more and more popular nowadays due to their easy deployment and wide spread of Wi-Fi interface cards. A Wi-Fi Alliance report finds that 1.2 million 802.11 chipsets will be produced in 2006. Parallel to technological development, a flurry of analytical studies appeared in communication literature. Experimental results and theoretical studies show that wireless networks may enter a saturation regime characterized by a highly suboptimal medium utilization. More specifically, standard rate adaptation mechanisms reduce transmission rates when multiple packet loss occurs. Yet if the packet loss is due to collision rather than bad channel (which is the working assumption for the rate adaptation mechanism) then the controller induces a higher probability of collision which snowballs in turn into an even lower throughput. Such a mechanism is used by the Automatic Rate Fallback (ARF) algorithm used in WLAN-II products from Lucent which assumes all packet kiss are due to bad channel.
Here, a method is provided for detecting when saturation occurs in 802.11 wireless networks. The method computes a simple, efficiently computable, formula based on “saturation”, as described below, discriminating features as inputs in order to predict saturation. The formula represents a classification boundary of saturation vs. non-saturation. The system classification boundary of saturation vs. non-saturation evolves from level curves with respect to load, interference or frame error rates, and the more the one of these conditions worsens the more the saturation boundary is approached. The consequences are very important in determining that the system approaches salutation, and also determining the cause of saturation: bad channel conditions or congestion or both.
Consider an 802.11e network formed of an Access Point (AF), and several stations (STA's). We will consider several Access Categories (AC) of the four AC's specified in 802.11e standard.
In the following, several scenarios are presented and comment on each of them if, and when, saturation is reached:
A. Single Connection (i.e. One Way)
Assume there is only one AP and one STA, and except for control frames, the data is transmitted only on the uplink. AP to STA (or, alternatively, only on the downlink, STA to AP). At low load, throughput is proportional to the load. The throughput then increases monotonically with load (load is MAC layer packet arrival rate at sender from its application layer). Starting with some load, the throughput remains constant indicating a plateau. However for the purpose of this project, this behavior is not considered saturation.
One characteristics of saturation (in our interpretation) is having packet collisions. In the one-link case there are no packet collisions (except maybe with interferers, which are not considered in this scenario), and as such, this case is not representative to saturation.
B. Link vs. Network
Consider the following scenario: the BSS (Basic service set) has three stations (STAs): two with high loads, and a third STA with a low load. The two STAs compete for the channel, and in this process create many packet collisions (and retransmissions). The third station, even though its packet transmissions may suffer multiple retransmissions, achieves the desired throughput, albeit with a larger delay. By increasing the first two STA loads the total throughput achieves a maximum value after which it decreases substantially by the cascading effect mentioned above. Then the saturation limit is achieved. The third station link throughput may not be affected. However, consider this case as network saturation.
A conclusion of this case is that saturation is a property of the network and not of individual links. Thus the network can be in saturation or not, and not a particular link.
C. Packet Collisions and Saturation
Consider a typical network scenario: one access point (AP) and several STAs. For moderate loads, when throughput is still a monotonically increasing function of load, packets may suffer collisions with some rate. An increase in the loads will produce an increase in the packet collision rate. Once the peak throughput is achieved, the packet collision rate keeps increasing with the load, however the throughput starts decreasing toward its saturation value.
Thus, the packet collision rate is a proxy for STAs loads and may be a good indicator of the presence of saturation.
All these aspects of the problem suggest the following definition of saturation:                A wireless network is in saturation if there is a set of decreases in the packet arrived rules at each station's MAC that produces an increase in the total throughput.        
In accordance with the present invention, a method is provided for measuring degree of packet congestion on a channel of a packet communication network. The method includes: during a training mode, generating an mathematical relationship between the degree of packet congestion on the channel and a plurality of measurable features of the network over a plurality of network conditions; and, during a subsequent normal operating mode, periodically measuring the plurality of measurable features and applying the generated mathematical relationship to such periodically measured plurality of measurable features to determine actual degree of congestion on the channel.
In one embodiment, the degree of packet congestion on the channel is saturation level of the channel.
In one embodiment, saturation level is a function of packet arrival rate at a receiver on the channel and total packet throughput on the channel.
In one embodiment, the function is that if there is a set of decreases in the packet arrival rates at each receiver that produces an increase in the total throughput, die channel is at the saturation level of the channel.
In one embodiment, the measurable features of the network include at least one of: time delay between transmission starts of a station on the channel and terminations of the previously transmitted packer from such station; the fraction of time the channel is busy with transmissions, regardless of the origin of the transmission, or whether packets were correctly transmitted and received; and, average number of packet transmission retries on the channel.
The details of one or more embodiments of the invention are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the invention will be apparent from the description and drawings, and from the claims.
Like reference symbols in the various drawings indicate like elements.